package com.sss.hloster03;
import java.util.Scanner;

public class InsertSort {// 直接插入，运用二分查找方法

	public static void main(String[] args) {
		insertSort();
	}

	/**
	 * 插入排序算法测试
	 */
	public static void insertSort() {
		// 初始化数组
		int[] arr = initArr();
		// 插入排序算法处理
		doInsertSort3(arr);
		// 显示打印结果
		printArr(arr);
	}

	/**
	 * 插入排序（从小到大）
	 */
	private static void doInsertSort3(int[] arr) {
		// 插入排序
		// 需要进行N轮的插入操作(N个数，需要N-1轮处理即可有序)
		for (int i = 0; i < arr.length - 1; i++) {
			// 当前需要插入的数的下标是 i+1
			// 取出需要插入的数
			int temp = arr[i + 1];
			// 使用二分查找确定插入位置
			int insertIndex = binarySearchIndex(arr, 0, i, temp);
			// 如果二分查找结果不为-1，则说明需要进行移动插入操作
			for (int j = i; j >= insertIndex; j--) {
				// 依次往后挪动
				arr[j + 1] = arr[j];
			}
			// 将需要插入的数temp，放入插入的位置insertIndex
			arr[insertIndex] = temp;
		}

	}

	/**
	 * 二分查找算法【前提条件，必须是有序序列】为插入排序查找插入位置服务【不等判定】
	 * 
	 * @param arr       被查找的数组
	 * @param searchVal 被查找的值
	 * @param begin     查找范围的开始下标
	 * @param end       查找范围的结束下标
	 * @return 可以插入的位置
	 */
	public static int binarySearchIndex(int[] arr, int begin, int end, int searchVal) {

		// 结束条件:只剩一个元素时就可以去定插入位置了，此时递归结束
		if (begin == end) {
			// 返回插入的位置
			if (searchVal < arr[begin]) {
				// 插入语在当前元素之前
				return begin;
			} else {
				// 插入当前元素之后
				return begin + 1;
			}
		}

		// 取出中间元素
		int mid = (begin + end) / 2;
		// 取出中间元素的值
		int midVal = arr[mid];
		// 结束条件：找到了
		if (searchVal == midVal) {
			// 找到了，返回找到的位置(重复元素，放在重复元素之后)
			return mid + 1;
		} else if (searchVal > midVal) {
			// 继续递归调用, 递归右半部分
			return binarySearchIndex(arr, mid + 1, end, searchVal);
		} else {
			// 继续递归调用,递归左半部分
			return binarySearchIndex(arr, begin, mid - 1, searchVal);
		}
	}

	/**
	 * 插入排序（从小到大）
	 */
	private static void doInsertSort2(int[] arr) {
		// 插入排序
		// 需要进行N轮的插入操作(N个数，需要N-1轮处理即可有序)
		for (int i = 0; i < arr.length - 1; i++) {
			// 当前需要插入的数的下标是 i+1
			// 取出需要插入的数
			int temp = arr[i + 1];
			// 确定插入位置：从后往前找，一边找一遍挪动
			// 查找位置的起始值为 i
			int insertIndex = i;
			while (insertIndex >= 0 && temp < arr[insertIndex]) {
				// 当前元素向后移动一个位置
				arr[insertIndex + 1] = arr[insertIndex];
				insertIndex--;
			}
			// while循环结束之后，insertIndex+1就是 下标为 i+1 这个数temp的插入位置
			// 将需要插入的数temp，放入插入的insertIndex+1位置
			arr[insertIndex + 1] = temp;
		}

	}

	/**
	 * 插入排序（从小到大）
	 */
	private static void doInsertSort(int[] arr) {
		// 插入排序
		// 需要进行N轮的插入操作(N个数，需要N-1轮处理即可有序)
		for (int i = 0; i < arr.length - 1; i++) {
			// 当前需要插入的数的下标是 i+1
			// 取出需要插入的数
			int temp = arr[i + 1];
			// 确定插入位置（可以考虑使用二分查找）
			// 每次从前往后确定插入位置，查找位置的初始值为0
			int insertIndex = 0;
			while (insertIndex < i + 1 && temp > arr[insertIndex]) {
				insertIndex++;
			}
			// while循环结束之后，insertIndex就是 下标为 i+1 这个数的插入位置
			// 挪到插入位置insertIndex之后有序列表中的所有的数，向后移动一位 ，需要挪动的最后一个数的下标是 i， 也就是把下标为i的数向后挪动到下标为
			// i+1 的位置
			for (int j = i; j >= insertIndex; j--) {
				// 依次往后挪动
				arr[j + 1] = arr[j];
			}
			// 将需要插入的数temp，放入插入的位置insertIndex
			arr[insertIndex] = temp;
		}

	}

	/**
	 * 初始化排序的数组
	 * 
	 * @return 被排序的数组
	 */
	private static int[] initArr() {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入需要排序的数组的元素个数：");
		// 数组个数
		int count = sc.nextInt();
		// 创建数组
		int[] arr = new int[count];
		// 初始化数组
		for (int i = 0; i < count; i++) {
			System.out.println("请输入数组的第" + (i + 1) + "个元素的值：");
			int input = sc.nextInt();
			arr[i] = input;
		}

		// 返回值
		return arr;
	}

	/**
	 * 打印数组元素内容
	 * 
	 * @param arr 被打印数组
	 */
	private static void printArr(int[] arr) {
		for (int i : arr) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
	}
}
